package algorithm_demo.sort;

import java.util.Arrays;

/**
 * 计数排序
 * <p>
 * 计数排序 (Counting Sort)计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
 * 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
 * <p>
 * 计数排序 (Counting sort) 是一种稳定的排序算法。
 * 计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。它只能对整数进行排序。
 * <p>
 * 算法步骤
 * 1. 找出数组中的最大值 max、最小值 min；
 * 2. 创建一个新数组 C，其长度是 max-min+1，其元素默认值都为 0；
 * 3. 遍历原数组 A 中的元素 A[i]，以 A[i]-min 作为 C 数组的索引，以 A[i] 的值在 A 中元素出现次数作为 C[A[i]-min] 的值；
 * 4. 对 C 数组变形，新元素的值是该元素与前一个元素值的和，即当 i>1 时 C[i] = C[i] + C[i-1]；
 * 5. 创建结果数组 R，长度和原始数组一样。
 * 6. 从后向前遍历原始数组 A 中的元素 A[i]，使用 A[i] 减去最小值 min 作为索引，在计数数组 C 中找到对应的值 C[A[i]-min]，C[A[i]-min]-1
 * 就是 A[i] 在结果数组 R 中的位置，做完上述这些操作，将 count[A[i]-min] 减小 1。
 *
 *
 * 算法分析
 * 当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n+k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），
 * 这使得计数排序对于数据范围很大的数组，需要大量额外内存空间。
 * - 稳定性 ：稳定
 * - 时间复杂度 ：最佳：O(n+k) 最差：O(n+k) 平均：O(n+k)
 * - 空间复杂度 ：O(k)
 *
 * @author Api
 * @date 2022/11/19 23:12
 */
public class CountingSort {


    public static void main(String[] args) {
        int[] arr = new int[]{2, 54, 3, 4, 6, 1, 2, 7, 5, 6};
        int[] ints = countingSort(arr);
        System.out.println(Arrays.toString(ints));
    }

    public static int[] getMaxAndMin(int[] arr) {
        int maxValue = arr[0];
        int minValue = arr[0];
        for (int j : arr) {
            if (j > maxValue) {
                maxValue = j;
            } else if (j < minValue) {
                minValue = j;
            }
        }
        return new int[]{minValue, maxValue};
    }

    public static int[] countingSort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int[] extremum = getMaxAndMin(arr);
        int minValue = extremum[0];
        int maxValue = extremum[1];
        int[] countArr = new int[maxValue - minValue + 1];
        int[] result = new int[arr.length];

        for (int j : arr) {
            countArr[j - minValue] += 1;
        }

        for (int i = 1; i < countArr.length; i++) {
            countArr[i] += countArr[i - 1];
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            int idx = countArr[arr[i]-minValue]-1;
            result[idx] = arr[i];
            countArr[arr[i]-minValue]-=1;
        }
        return result;
    }
}
